public class Solution206 {
    ListNode h;

    public ListNode reverseList(ListNode head) {
        /*if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;*/
        h = new ListNode();
        reverse(head);
        return h.next;
    }

    ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode t = reverse(head.next);
        if (t == null) {
            h.next = head;
        } else {
            t.next = head;
            head.next = null;
        }
        return head;
    }
}
